/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: GodK
 * Date: 2024-03-28
 * Time: 11:14
 */
public class Main {
      class ListNode {
          int val;
          ListNode next;
          ListNode(int x) {
              val = x;
              next = null;
         }
      }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode l1 = headA;
        ListNode l2 = headB;
        int i = 0;
        int j = 0;
        while(l1 != null){
            i++;
            l1 = l1.next;
        }
        while(l2 != null){
            j++;
            l2 = l2.next;
        }
        l1 = headA;
        l2 = headB;
        i = i - j;
        if(i < 0){
            i = -i;
            l2 = headA;
            l1 = headB;
        }
        while(i > 0){
            l1 = l1.next;
            i--;
        }
        while(l1 != l2){
            l1 = l1.next;
            l2 = l2.next;
        }
        if(l1 == null)return null;
        return l1;
    }
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null)return null;
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
    public boolean chkPalindrome(ListNode head) {
        if(head == null)return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }
        while(head != slow){
            if(head.val != slow.val)return false;
            if(head.next == slow)return true;
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}
